package path_finding;

import java.util.*;

public class BFS implements PathFinding {
    public boolean allowDiagonal = false;
    public Heuristic heuristic = (fromX, fromY, toX, toY) -> Math.abs(fromX - toX) + Math.abs(fromY - toY);
    public XyTrans xyTrans;

    @Override
    public List<Integer> findPath(int [][] grid, int startX, int startY, int endX, int endY, int [][]visited) {
        Queue<Node> queue = new ArrayDeque<>();
        Map<Integer, Node> visitedNodes = new HashMap<>();
        Node start = new Node(xyTrans.toId(startX, startY));
        queue.add(start);
        visitedNodes.put(start.id, start);
        int target = xyTrans.toId(endX, endY);

        Node endNode = null;
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node.id == target) {
                endNode = node;
                break;
            }
            List<Integer> neighbors = new ArrayList<>(8);
            getNeighbors(node.id, grid, neighbors);

            for (int neighbor : neighbors) {
                if (visitedNodes.containsKey(neighbor)) continue;
                int[] xy = xyTrans.toXy(neighbor);
                visited[xy[0]][xy[1]] = 1;
                Node newNode = new Node(neighbor, node);
                queue.add(newNode);
                visitedNodes.put(neighbor, newNode);
            }
        }

        List findPath = new ArrayList();
        while (endNode != null) {
            findPath.add(endNode.id);
            endNode = endNode.parent;
        }
        Collections.reverse(findPath);
        return findPath;
    }

    private void getNeighbors(int nodeId, int [][] grid, List<Integer> neighbors) {
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        // 对角线方向
        if (allowDiagonal) {
            int[] diagonalDx = {-1, -1, 1, 1};
            int[] diagonalDy = {-1, 1, -1, 1};
            for (int i = 0; i < 4; i++) {
                addNeighborIfValid(nodeId, diagonalDx[i], diagonalDy[i], grid, neighbors);
            }
        }

        // 四方向
        for (int i = 0; i < 4; i++) {
            addNeighborIfValid(nodeId, dx[i], dy[i], grid, neighbors);
        }
    }

    private void addNeighborIfValid(int nodeId, int dx, int dy, int[][] grid, List<Integer> neighbors) {
        int []xy = xyTrans.toXy(nodeId);
        int newX = xy[0] + dx;
        int newY = xy[1] + dy;

        if (newX >= 0 && newX < grid.length &&
                newY >= 0 && newY < grid[0].length &&
                grid[newX][newY] == 0) { // 0 表示可通行
            neighbors.add(xyTrans.toId(newX, newY));
        }
    }

    @Override
    public void setAllowDiagonal(boolean allow) {
        allowDiagonal = allow;
    }

    @Override
    public void setHeuristic(Heuristic heuristic) {
        this.heuristic = heuristic;
    }

    @Override
    public void setXyTrans(XyTrans xyTrans) {
        this.xyTrans = xyTrans;
    }

    private static class Node {
        public int id;
        public Node parent;
        public Node(int id) {
            this.id = id;
        }
        public Node(int id, Node parent) {
            this.id = id;
            this.parent = parent;
        }
    }
}
